图解 ArrayDeque 比 LinkedList 快
hi 这是 dhl 的第 44 篇文章
个人微信: hi-dhl
在之前的两篇文章中主要分析了 Java 栈的缺点 ，为什么不推荐使用 Java 栈 ，以及 为什么不推荐直接使用 ArrayDeque 代替 Java Stack 。更多内容点击下方链接前去查看。
接口 Deque 的子类 ArrayDeque ，作为栈使用时比 Stack 快，因为原来的 Java 的 Stack 继承自 Vector，而 Vector 在每个方法中都加了锁，而 Deque 的子类 ArrayDeque 并没有锁的开销。
接口 Deque 还有另外一个子类 LinkedList。LinkedList 基于双向链表实现的双端队列，ArrayDeque 作为队列使用时可能比 LinkedList 快。
而这篇文章主要来分析，为什么 ArrayDeque 比 LinkedList 快。在开始分析之前，我们需要简单的了解一下它们的数据结构的特点。
接口 Deque
接口 Deque 继承自 Queue 即队列, 在 Java 中队列有两种形式，单向队列（ AbstractQueue ） 和 双端队列（ Deque ），单向队列效果如下所示，只能从一端进入，另外一端出去。
而今天主要介绍双端队列（ Deque ）, Deque 是双端队列的线性数据结构, 可以在两端进行插入和删除操作，效果如下所示。
双端队列（ Deque ）的子类分别是 ArrayDeque 和 LinkedList，ArrayDeque 基于数组实现的双端队列，而 LinkedList 基于双向链表实现的双端队列，它们的继承关系如下图所示。
接口 Deque 和 Queue 提供了两套 API ，存在两种形式，分别为抛出异常，和不抛出异常，返回一个特殊值 null 或者布尔值 ( true | false )。
| 操作类型 | 抛出异常 | 返回特殊值 |
|---|---|---|
| 插入 | addXXX(e) | offerXXX(e) |
| 移除 | removeXXX() | pollXXX() |
| 查找 | element() | peekXXX() |
ArrayDeque
ArrayDeque 是基于（循环）数组的方式实现双端队列，数组初始化容量为 16（JDK 8），结构图如下所示。
ArrayDeque 具有以下特点：
因为双端队列只能在头部和尾部插入或者删除元素，所以时间复杂度为 O(1)，但是在扩容的时候需要批量移动元素，其时间复杂度为O(n)扩容的时候，将数组长度扩容为原来的 2 倍，即 n << 1数组采用连续的内存地址空间，所以查询的时候，时间复杂度为 O(1)它是非线程安全的集合
LinkedList
LinkedList 基于双向链表实现的双端队列，它的结构图如下所示。
LinkedList 具有以下特点：
LinkedList是基于双向链表的结构来存储元素，所以长度没有限制，因此不存在扩容机制由于链表的内存地址是非连续的，所以只能从头部或者尾部查找元素，查询的时间复杂为 O(n)，但是 JDK 对LinkedList做了查找优化，当我们查找某个元素时，若index < (size / 2)，则从head往后查找，否则从tail开始往前查找 , 但是我们在计算时间复杂度的时候，常数项可以省略，故时间复杂度O(n)
Node<E> node(int index) {
// size >> 1 等价于 size / 2
if (index < (size >> 1)) {
// form head to tail
} else {
// form tail to head
}
}
链表通过指针去访问各个元素，所以插入、删除元素只需要更改指针指向即可，因此插入、删除的时间复杂度 O(1)它是非线程安全的集合
最后汇总一下 ArrayDeque 和 LinkedList 的特点如下所示：
| 集合类型 | 数据结构 | 初始化及扩容 | 插入/删除时间复杂度 | 查询时间复杂度 | 是否是线程安全 |
|---|---|---|---|---|---|
| ArrqyDeque | 循环数组 | 初始化：16 扩容：2 倍 | 0(n) | 0(1) | 否 |
| LinkedList | 双向链表 | 无 | 0(1) | 0(n) | 否 |
为什么 ArrayDeque 比 LinkedList 快
了解完数据结构特点之后，接下来我们从两个方面分析为什么 ArrayDeque 作为队列使用时可能比 LinkedList 快。
从速度的角度：
ArrayDeque基于数组实现双端队列，而LinkedList基于双向链表实现双端队列，数组采用连续的内存地址空间，通过下标索引访问，链表是非连续的内存地址空间，通过指针访问，所以在寻址方面数组的效率高于链表。从内存的角度：虽然
LinkedList没有扩容的问题，但是插入元素的时候，需要创建一个Node对象, 换句话说每次都要执行new操作，当执行new操作的时候，其过程是非常慢的，会经历两个过程：类加载过程 、对象创建过程。类加载过程
会先判断这个类是否已经初始化，如果没有初始化，会执行类的加载过程 类的加载过程：加载、验证、准备、解析、初始化等等阶段，之后会执行 <clinit>()方法，初始化静态变量，执行静态代码块等等对象创建过程
如果类已经初始化了，直接执行对象的创建过程
对象的创建过程：在堆内存中开辟一块空间，给开辟空间分配一个地址，之后执行初始化，会执行
<init>()方法，初始化普通变量，调用普通代码块
接下来我们通过 算法动画图解 | 被 "废弃" 的 Java 栈，为什么还在用 文章中 LeetCode 算法题：有效的括号，来验证它们的执行速度，以及在内存方面的开销，代码如下所示：
class Solution {
public boolean isValid(String s) {
// LinkedList VS ArrayDeque
// Deque<Character> stack = new LinkedList<Character>();
Deque<Character> stack = new ArrayDeque<Character>();
// 开始遍历字符串
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// 遇到左括号，则将其对应的右括号压入栈中
if (c == '(') {
stack.push(')');
} else if (c == '[') {
stack.push(']');
} else if (c == '{') {
stack.push('}');
} else {
// 遇到右括号，判断当前元素是否和栈顶元素相等，不相等提前返回，结束循环
if (stack.isEmpty() || stack.poll() != c) {
return false;
}
}
}
// 通过判断栈是否为空，来检查是否是有效的括号
return stack.isEmpty();
}
}
正如你所看到的，核心算法都是一样的，通过接口 Deque 来访问，只是初始化接口 Deque 代码不一样。
// 通过 LinkedList 初始化
Deque<Character> stack = new LinkedList<Character>();
// 通过 ArrayDeque 初始化
Deque<Character> stack = new ArrayDeque<Character>();
结果如上所示，无论是在执行速度、还是在内存开销上 ArrayDeque 的性能都比 LinkedList 要好。
推荐阅读：
感谢大家帮忙 在看、点赞、分享 给身边更多的朋友
代码不止，文章不停
欢迎点击下方卡片关注我，查看最新技术文章
公众号简介：
hi 大家好，我是 DHL，专注分享最新技术原创文章，涉及 Kotlin、Jetpack、算法动画、系统源码 等等。
感谢你看到这里
就现在
给正在努力中的自己
点个 在看 吧↓↓↓
最后推荐长期更新和维护的项目：
个人博客，将所有文章进行分类，欢迎前去查看
https://hi-dhl.comKtKit 小巧而实用，用 Kotlin 语言编写的工具库，欢迎前去查看
https://github.com/hi-dhl/KtKit计划建立一个最全、最新的 AndroidX Jetpack 相关组件的实战项目 以及 相关组件原理分析文章，正在逐渐增加 Jetpack 新成员，仓库持续更新，欢迎前去查看
https://github.com/hi-dhl/AndroidX-Jetpack-PracticeLeetCode / 剑指 offer / 国内外大厂面试题 / 多线程 题解，语言 Java 和 kotlin，包含多种解法、解题思路、时间复杂度、空间复杂度分析
剑指 offer：https://offer.hi-dhl.com
LeetCode：https://leetcode.hi-dhl.com